package LeetCodeHot100;

import java.util.Arrays;

/**
 * 搜索旋转排序数组
 整数数组 nums 按升序排列，数组中的值 互不相同 。
 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

 思路： 首先，我们想到了二分，但是二分必须是排序的数组，
        第一种思路就是先排序，然后利用二分搜索， 思索一下时间复杂度，o(llogn)

 重点重点重点！！！！！！！！
 记住， 旋转数组， 这个数组本来就是有序的！！！！ 它只不过是旋转了一下， 无论怎么旋转，这个数组的只要二分，就证明，它总有一半是有序的
 然后，我们就可以通过这个有序做文章，继续二分。

 所以，思路就是，如果最中间的数小于最右边的数据，那么就代表着右边有序，若中间的数大于最右边的数据，则左边有序，我们只要判断那边有序，
     就可以只在有序的半段里用首尾两个数组来判断目标值是否在这一区域内，这样就可以确定保留在哪边。

 还有一个点，使用二分的前提是有序，记住了，只有有序才能使用二分。

 */
public class LeetCode33 {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if(n == 0){
            return -1;
        }
        int l = 0, r = nums.length-1;
        int res = -1;

        while (l <= r){
            int mid = l+(r-l)/2;
            if(nums[mid] == target){
                res = mid;
                break;
            }else if(nums[mid] < nums[r]){   // 证明右半边有序，所以可以在这里继续二分
                if(nums[mid] < target && nums[r] >= target){
                    l = mid+1;
                }else { // 去左边找
                    r = mid-1;
                }
            }else {  // 证明左半边有序，所以可以在这里继续二分
                if(nums[mid] > target && nums[l] <= target){
                    r = mid -1;
                }else {  // 去右边找
                    l = mid +1;
                }
            }
        }
        return res;
    }
}
